W7–W8. Преобразователи с магазином (PDT), операции над языками DPDA, теория автоматов и модели вычислений

1. Краткое содержание

1.1 Напоминание: конечные преобразователи (FST)

Прежде чем вводить более мощный преобразователь с магазином (PDT), полезно вспомнить, как работает конечный преобразователь (FST), поскольку PDT — его прямое обобщение.

Конечный преобразователь (FST) — это конечный автомат (FSA), дополненный механизмом вывода. Формально FST — это кортеж \(\langle Q, I, \delta, q_0, F, O, \eta \rangle\), где:

• \(\langle Q, I, \delta, q_0, F \rangle\) — обычный FSA (состояния, входной алфавит, функция переходов, начальное состояние, принимающие состояния);
• \(O\) — выходной алфавит — множество символов, которые могут записываться на выход;
• \(\eta : Q \times I \to O^*\) — функция перевода — она сопоставляет каждой паре «состояние — входной символ» выходную строку.

Важное замечание: функция \(\eta\) применяется только к строкам, которые принимаются базовым FSA. Если входная строка отвергается, её перевод не определён.

Как работает FST: при чтении каждого входного символа FST одновременно (a) меняет состояние (через \(\delta\)) и (b) записывает выходную строку (через \(\eta\)). На стрелке диаграммы переходов подпись имеет вид вход/выход, например a/A означает «прочитать \(a\) с входа, записать \(A\) на выход».

Пример — простой регистронный преобразователь:

Пусть \(L = \{x \in \{a, b\}^*\}\) (все строки над \(\{a,b\}\)) с переводом \(a \mapsto A\), \(b \mapsto B\).

У FST одно принимающее состояние \(q_0\) с петлями:

• \(q_0 \xrightarrow{a/A} q_0\): прочитать \(a\), вывести \(A\)
• \(q_0 \xrightarrow{b/B} q_0\): прочитать \(b\), вывести \(B\)

На входе \(aba\) FST выдаёт \(ABA\).

Пример — FST с ограниченной областью:

Пусть \(L = \{x \in \{a,b\}^* \mid \text{в } x \text{ нет символов } b\}\) с тем же переводом. Теперь FST имеет два состояния:

• \(q_0\) (принимающее): читает \(a\) и выводит \(A\); при чтении \(b\) переходит в непринимающее «стоковое» состояние \(q_1\)
• \(q_1\) (отвергающее): читает любой символ и выводит \(\varepsilon\) (строка всё равно будет отвергнута)

На входе \(aaa\) выход — \(AAA\). На входе \(aba\) строка отвергается — перевод не определён.

Ограничение FST: как и у FSA, память только конечная и фиксированная (текущее состояние). Нельзя обрабатывать языки, где нужен «счёт», например \(L = \{a^n b^n \mid n \geq 1\}\), если выход должен отслеживать, сколько \(a\) прочитано, чтобы выдать нужное число выходных символов. Нужен преобразователь с магазином (PDT).

1.2 Преобразователи с магазином (PDT)

1.2.1 Мотивация и наглядная картина

Преобразователь с магазином (PDT) расширяет автомат с магазином (PDA) выходной лентой так же, как FST расширяет FSA. PDT использует стек не только для распознавания языка (как в PDA), но и для помощи переводу: в стеке хранится промежуточная информация, нужная для корректного выхода.

Архитектура PDT состоит из четырёх частей:

• Входная лента: только для чтения; символы читаются слева направо
• Конечное управление: конечное множество состояний и логика переходов
• Стек: память LIFO (последним пришёл — первым ушёл), может неограниченно расти
• Выходная лента: только для записи; к ней дописываются выходные символы

Архитектура преобразователя с магазином: входная лента, конечное управление, стек и выходная лента

Стек — разрушающая память: символ, снятый со стека, исчезает. В этом и сила PDT, и его принципиальное ограничение.

Один переход PDT за атомарный шаг: читает входной символ (или \(\varepsilon\)), смотрит вершину стека, меняет состояние, переписывает вершину стека и пишет на выходную ленту.

1.2.2 Нотация переходов

Переход из состояния \(q\) в состояние \(p\) изображается стрелкой с подписью:

\[i,\, A / \alpha,\, w\]

где:

• \(i \in I \cup \{\varepsilon\}\) — прочитанный входной символ (или \(\varepsilon\) для тихого шага)
• \(A \in \Gamma\) — символ стека, снимаемый с вершины
• \(\alpha \in \Gamma^*\) — строка, вталкиваемая на стек (вместо \(A\))
• \(w \in O^*\) — строка, записываемая на выходную ленту

Альтернативная нотация отделяет двоеточием часть стека от выхода:

\[i,\, A / \alpha : w\]

В литературе встречаются обе; смысл один.

То есть \(\delta(q, i, A) = (p, \alpha)\) и \(\eta(q, i, A) = w\) на диаграмме объединяются в подпись \(i, A/\alpha, w\).

1.2.3 Формальное определение

Преобразователь с магазином — это 9-кортеж:

\[\text{PDT} = \langle Q,\, I,\, \Gamma,\, \delta,\, q_0,\, Z_0,\, F,\, O,\, \eta \rangle\]

где:

• \(Q\) — конечное множество состояний
• \(I\) — конечный входной алфавит
• \(\Gamma\) — конечный алфавит стека
• \(\delta: Q \times (I \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^*)\) — функция переходов (частичная; образ — конечные подмножества)
• \(q_0 \in Q\) — начальное состояние
• \(Z_0 \in \Gamma\) — начальный символ стека (маркер дна)
• \(F \subseteq Q\) — принимающие состояния
• \(O\) — конечный выходной алфавит
• \(\eta: Q \times (I \cup \{\varepsilon\}) \times \Gamma \to O^*\) — функция перевода (определена только там, где определена \(\delta\))

Замечания:

• \(Q, I, \Gamma, \delta, q_0, Z_0, F\) — те же компоненты, что у обычного PDA-«распознавателя».
• \(\eta\) определена только там, где определена \(\delta\) — на неопределённых переходах выхода нет.
• Стек может быть нужен по двум разным причинам: (a) для распознавания языка, и/или (b) для перевода.

1.2.4 Конфигурации и переходы

Конфигурация PDT — это 4-кортеж:

\[c = \langle q,\, x,\, \gamma,\, z \rangle\]

где:

• \(q \in Q\) — текущее состояние управления
• \(x \in I^*\) — непрочитанный остаток входной строки
• \(\gamma \in \Gamma^*\) — текущее содержимое стека (верхний символ записан первым)
• \(z \in O^*\) — строка, уже записанная на выходную ленту

Переходы между конфигурациями:

• Шаг по входу (потребление символа \(i\)): если \(\delta(q, i, A) = (q', \alpha)\) и \(\eta(q, i, A) = w\), то: \[\langle q,\, iy,\, A\gamma,\, z \rangle \vdash \langle q',\, y,\, \alpha\gamma,\, zw \rangle\]
• \(\varepsilon\)-шаг (тихий, вход не читается): если \(\delta(q, \varepsilon, A) = (q', \alpha)\) и \(\eta(q, \varepsilon, A) = w\), то: \[\langle q,\, x,\, A\gamma,\, z \rangle \vdash \langle q',\, x,\, \alpha\gamma,\, zw \rangle\]

Важно: при \(\varepsilon\)-переходе непрочитанный вход \(x\) не меняется (символ с входа не потребляется).

1.2.5 Условие принятия

PDT переводит строку \(x\) в \(z = \tau(x)\) тогда и только тогда, когда, стартуя из \(c_0 = \langle q_0, x, Z_0, \varepsilon \rangle\), он достигает финальной конфигурации \(c_F = \langle q_f, \varepsilon, \gamma, z \rangle\) с \(q_f \in F\) (весь вход прочитан, состояние принимающее):

\[\forall x \in I^*:\quad x \in L \wedge z = \tau(x) \iff \langle q_0, x, Z_0, \varepsilon \rangle \vdash^* \langle q_f, \varepsilon, \gamma, z \rangle \text{ для некоторого } q_f \in F\]

Это согласуется с тем, как устроен перевод в FST: перевод \(x\) определён только если строка \(x\) принята.

1.3 Примеры PDT

1.3.1 Перевод \(a^n b^n \to A^n B^n\)

Пусть \(L = \{a^n b^n \mid n \geq 1\}\) и \(\tau(a^n b^n) = A^n B^n\) (каждый символ «в верхний регистр»).

Идея: стек считает число \(a\) (вталкивать \(A\) на каждое \(a\)), затем проверяются \(b\) с выводом \(B\) на каждое совпадение с \(A\).

Состояния \(q_0, q_1, q_2, q_3\) (принимающие):

• \(q_0 \to q_1\): переход \(a, Z_0 / AZ_0, A\) — первое \(a\), втолкнуть \(A\) над \(Z_0\), вывести \(A\)
• \(q_1 \circlearrowleft\): \(a, A / AA, A\) — каждое следующее \(a\), ещё \(A\) на стек, вывести \(A\)
• \(q_1 \to q_2\): \(b, A / \varepsilon, B\) — начало чтения \(b\), снять один \(A\), вывести \(B\)
• \(q_2 \circlearrowleft\): \(b, A / \varepsilon, B\) — каждое следующее \(b\), снять \(A\), вывести \(B\)
• \(q_2 \to q_3\): \(\varepsilon, Z_0 / Z_0, \varepsilon\) — если после входа наверху \(Z_0\), принять (без выхода)

PDT для перевода aⁿbⁿ → AⁿBⁿ

На входе \(aba\): отвергается (не в \(L\)), перевод не определён.

1.3.2 Перевод \(a^n b^n \to b^n\)

Пусть \(L = \{a^n b^n \mid n > 0\}\) и \(\tau(a^n b^n) = b^n\) (на выход только «\(b\)-часть»).

Идея: на фазе вталкивания (\(a\)) ничего не выводить. На фазе снятия (\(b\)) выводить \(b\) на каждое совпадение с \(A\).

• \(q_0\): \(a, Z_0 / AZ_0, \varepsilon\) и \(a, A / AA, \varepsilon\) — вталкивать \(A\) без выхода
• \(q_0 \to q_1\): \(b, A / \varepsilon, b\) — первое \(b\), снять \(A\), вывести \(b\)
• \(q_1 \circlearrowleft\): \(b, A / \varepsilon, b\) — дальше \(b\), выводить \(b\)
• \(q_1 \to q_F\): \(\varepsilon, Z_0 / Z_0, \varepsilon\) — принять

Итог: \(a^n b^n \mapsto b^n\).

1.3.3 Перевод \(a^n b^n \to b^n a^n\)

Пусть \(L = \{a^n b^n \mid n > 0\}\) и \(\tau(a^n b^n) = b^n a^n\) (поменять блоки местами).

Идея: на фазе \(a\) выводить \(b\) (заранее «готовить» выход). На фазе \(b\) выводить \(a\) на каждое совпадение.

• \(q_0\): \(a, Z_0 / AZ_0, b\) и \(a, A / AA, b\) — вталкивать \(A\), на каждое \(a\) выводить \(b\)
• \(q_0 \to q_1\): \(b, A / \varepsilon, a\) — снять \(A\), вывести \(a\)
• \(q_1 \circlearrowleft\): \(b, A / \varepsilon, a\)
• \(q_1 \to q_F\): \(\varepsilon, Z_0 / Z_0, \varepsilon\) — принять

Итог: \(a^n b^n \mapsto b^n a^n\). Стек даёт «перевёрнутые» переводы, недоступные FST.

1.3.4 Перевод \(wc \to w^R\) (обращение строки)

Пусть \(L = \{wc \mid w \in \{a,b\}^+\}\) и \(\tau(wc) = w^R\) (обращение \(w\), \(c\) — разделитель).

Идея (СНАЧАЛА ВТАЛКИВАНИЕ — ПОТОМ СНЯТИЕ): пока читается \(w\), каждый символ вталкивается в стек, без выхода. При разделителе \(c\) прекращаем вталкивание и начинаем снимать — выводим каждым снятием. LIFO даёт символы в обратном порядке.

• Состояние \(q_0\) (ФАЗА ВТАЛКИВАНИЯ — БЕЗ ВЫХОДА):
  • \(a, Z_0 / AZ_0, \varepsilon\); \(a, A / AA, \varepsilon\); \(a, B / AB, \varepsilon\)
  • \(b, Z_0 / BZ_0, \varepsilon\); \(b, B / BB, \varepsilon\); \(b, A / BA, \varepsilon\)
• Переход \(q_0 \to q_1\) (КОНЕЦ ВТАЛКИВАНИЯ):
  • \(c, A / \varepsilon, a\); \(c, B / \varepsilon, b\)
• Состояние \(q_1\) (ФАЗА СНЯТИЯ — ФОРМИРОВАНИЕ ВЫХОДА):
  • \(\varepsilon, A / \varepsilon, a\); \(\varepsilon, B / \varepsilon, b\)
• Переход \(q_1 \to q_2\) (принимающее): \(\varepsilon, Z_0 / Z_0, \varepsilon\)

PDT для обращения wc → wᴿ

На входе \(abc\): в стек \(A\), затем \(B\), затем \(c\) — снять \(B\) (выход \(b\)), снять \(A\) (выход \(a\)). Итоговый выход: \(ba = (ab)^R\). ✓

Стек позволяет переводы, где выход не следует строго слева направо по входу.

1.4 Свойства замкнутости языков DPDA

Перейдём от преобразователей к базовому вопросу теории формальных языков: какие операции сохраняют класс языков, распознаваемых детерминированными автоматами с магазином (DPDA)?

Это вопрос свойств замкнутости. Класс языков \(\mathcal{C}\) замкнут относительно операции \(\mathcal{O}\), если применение \(\mathcal{O}\) к языкам из \(\mathcal{C}\) всегда даёт язык из \(\mathcal{C}\).

Формально: \(\mathcal{C}\) замкнут относительно \(\mathcal{O}\), если для любых \(L_1, \ldots, L_n \in \mathcal{C}\) выполнено \(\mathcal{O}(L_1, \ldots, L_n) \in \mathcal{C}\).

Зачем это нужно: для регулярных языков (FSA) класс замкнут по четырём стандартным операциям — объединение, пересечение, дополнение и разность. Интересно, есть ли у детерминированных контекстно-свободных языков (DPDA) такие же удобные свойства.

Свойства замкнутости: FSA и DPDA

Итог (сводная таблица):

	\(\cup\)	\(\cap\)	\(\setminus\)	\({}^c\)
FSA (регулярные)	да	да	да	да
DPDA (дет. КС-языки)	нет	нет	нет	да

Далее по очереди разберём каждую операцию и причину результата.

1.4.1 Замкнутость по объединению: НЕТ

Утверждение: класс языков DPDA не замкнут по объединению.

Контрпример: два языка над \(\Sigma = \{a, b\}\):

\[L_1 = \{a^n b^n \mid n \geq 1\}, \quad L_2 = \{a^n b^{2n} \mid n \geq 1\}\]

И \(L_1\), и \(L_2\) по отдельности распознаются DPDA (каждый — детерминированный контекстно-свободный язык). Но их объединение

\[L_1 \cup L_2 = \{a^n b^n \mid n \geq 1\} \cup \{a^n b^{2n} \mid n \geq 1\}\]

не распознаётся ни одним DPDA.

Наглядно: «проблема подготовки стека». Пока DPDA читает \(a\), он должен заранее — на фазе вталкивания — решить, готовить стек к \(n\) символам \(b\) (для \(L_1\)) или к \(2n\) (для \(L_2\)). Но это можно понять только после всех \(a\) и начала \(b\). К этому моменту содержимое стека уже зафиксировано. NPDA мог бы «ветвиться», DPDA — нет.

Точнее: после \(a^n\) в стеке закодировано \(n\). Читая \(b\), нельзя одновременно проверять и «против \(n\)», и «против \(2n\)» — нужно зафиксировать интерпретацию.

В отличие от регулярных: для FSA объединение строится декартовым произведением; для DPDA общего аналога нет — стеки для \(L_1\) и \(L_2\) могут быть несовместимы.

\(\Rightarrow\) DPDA не замкнут по \(\cup\).

1.4.2 Замкнутость по пересечению: НЕТ

Утверждение: DPDA не замкнут по пересечению.

Контрпример: языки над \(\Sigma = \{a, b, c\}\):

\[L_1 = \{a^n b^n c^m \mid n, m > 0\}, \quad L_2 = \{a^m b^n c^n \mid n, m > 0\}\]

Оба распознаются DPDA:

• \(L_1\): считать \(a\), по одному сопоставлять \(b\), затем принять любое положительное число \(c\).
• \(L_2\): пропустить любое положительное число \(a\), считать \(b\), сопоставлять \(c\) один к одному.

Пересечение:

\[L_1 \cap L_2 = \{a^n b^n c^n \mid n > 0\}\]

Классический язык \(\{a^n b^n c^n\}\), который не распознаётся ни одним PDA (даже недетерминированным) — лемма Бар-Хиллеля (накачка) для КС-языков. Тем более не DPDA.

\(\Rightarrow\) DPDA не замкнут по \(\cap\).

Через дополнение: алгебраически, законы де Моргана:

\[A \cup B = (A^c \cap B^c)^c\]

Так как DPDA замкнут по дополнению (ниже), при замкнутости по пересечению получилась бы замкнутость по объединению — противоречие.

1.4.3 Замкнутость по дополнению: ДА

Утверждение: DPDA замкнут по дополнению.

Теорема: если \(L \in \mathbf{DPDA}\), то \(L^c \in \mathbf{DPDA}\).

Почему для NPDA дополнение «ломается», а для DPDA — нет: у NPDA строка может отвергаться на всех путях, но приниматься на другом; недетерминизм мешает просто «инвертировать» принятие. У детерминированного PDA на каждый вход одна вычислимая ветка — принятые и отвергнутые строки разделимы.

Набросок построения — почему недостаточно поменять местами финальные состояния:

Для FSA дополнение: поменять финальные и нефинальные. У PDA наивный приём ломается из-за \(\varepsilon\)-переходов: на входе \(x\) машина в нефинальном \(q\), но \(\varepsilon\)-переходом доходит до финального \(q'\). После «обмена» \(q\) станет финальным — «дополненный» автомат тоже примет \(x\) — неверно.

Правильное построение — три шага:

1. Убрать циклы: привести DPDA к ациклическому виду — после прочтения всего входа дальнейших \(\varepsilon\)-ходов нет. Любой DPDA эквивалентен ациклическому DPDA (нетривиальный факт). Тогда проблема выше исчезает.
2. Полнота \(\delta\): сделать переходы везде определёнными, добавив непринимающее «мусорное» состояние \(q_{\text{err}}\) для всех «дыр». Тогда из каждой конфигурации ровно один следующий шаг.
3. Обмен финальных и нефинальных: раз машина после полного чтения входа останавливается в однозначном состоянии без \(\varepsilon\)-неоднозначности, обмен \(F\) и \(Q\setminus F\) даёт язык-дополнение.

Зачем ацикличность: иначе после конца входа возможны бесконечные \(\varepsilon\)-циклы через и финальные, и нефинальные состояния. С ацикличностью после исчерпания входа — одно ясное состояние.

\(\Rightarrow\) DPDA замкнут по \({}^c\).

1.4.4 Замкнутость по разности: НЕТ

Утверждение: DPDA не замкнут по разности множеств.

От противного: пусть замкнут по \(\setminus\). Для любых \(A, B\):

\[A \cap B = A \setminus B^c\]

По дополнению \(B^c \in \mathbf{DPDA}\). Тогда \(A \setminus B^c \in \mathbf{DPDA}\), значит \(A \cap B \in \mathbf{DPDA}\) — противоречие с незамкнутостью по \(\cap\).

\(\Rightarrow\) DPDA не замкнут по \(\setminus\).

Сравнение с регулярными: у FSA все четыре операции; у дет. КСЯ профиль асимметричен — только дополнение.

1.5 Лемма Бар-Хиллеля (накачка для КС-языков)

Лемма Бар-Хиллеля обобщает лемму о накачке с регулярных языков на контекстно-свободные. Как лемма о накачке для регулярных даёт необходимое условие регулярности, Бар-Хиллель даёт необходимое (но не достаточное) условие контекстно-свободности.

Лемма Бар-Хиллеля: если \(L \subseteq \Sigma^*\) — контекстно-свободный язык (распознаётся некоторым NPDA), то существует \(m \geq 1\) такое, что каждое \(w \in L\) с \(|w| \geq m\) представимо в виде:

\[w = x_1 x_2 x_3 x_4 x_5\]

причём:

1. \(|x_2 x_4| > 0\) (накачиваемые части не обе пусты)
2. \(|x_2 x_3 x_4| \leq m\) (окно накачки ограничено)
3. \(x_1 x_2^i x_3 x_4^i x_5 \in L\) для всех \(i \geq 1\)

В отличие от регулярной леммы (одна подстрока \(y\)), здесь накачиваются две подстроки — \(x_2\) и \(x_4\) — синхронно, на одно и то же \(i\). Это отражает вложенность выводов в КС-грамматиках.

Применение — \(\{a^n b^n c^n \mid n > 0\}\) не КС-язык:

\(L = \{a^n b^n c^n \mid n > 0\}\) не распознаётся ни одним PDA. Доказательство через Бар-Хиллель:

Пусть \(L\) КС; \(m\) — константа леммы. Возьмём \(w = a^m b^m c^m \in L\). Для любого разбиения \(w = x_1 x_2 x_3 x_4 x_5\) с \(|x_2 x_4| > 0\) и \(|x_2 x_3 x_4| \leq m\):

• \(x_2 x_3 x_4\) короткое, значит пересекает не больше двух из трёх блоков (\(a\), \(b\), \(c\)).
• Накачка вверх (\(i = 2\)) увеличивает не более двух типов символов, не все три поровну.
• Тогда \(x_1 x_2^2 x_3 x_4^2 x_5\) имеет неравные числа \(a\), \(b\), \(c\) — не в \(L\).

Противоречие. Значит \(L = \{a^n b^n c^n\}\) не контекстно-свободен.

1.6 Стек как разрушающая память и пределы PDA

1.6.1 Разрушающая и постоянная память

У PDA стек разрушающий: снятый символ не восстановить. Поэтому:

• PDA распознаёт \(\{a^n b^n\}\): \(n\) операций push на \(a\), затем по одному pop на каждый \(b\).
• PDA не распознаёт \(\{a^n b^n c^n\}\): для \(c\) снова нужно знать \(n\), а стек уже «использован» на \(b\).

Нужна постоянная (читаемая/записываемая) память — устройство, где ячейку можно прочитать без уничтожения. Это мотивация машин Тьюринга с неограниченной лентой чтения-записи вместо стека.

1.6.2 Иерархия языков

Иерархия языков: регулярные ⊂ КС ⊂ перечислимые

Иерархия по моделям:

• Регулярные ⊂ контекстно-свободные (КСЯ) ⊂ перечислимые (всё, что считает МТ)

Границы:

• \(\{a^n b^n \mid n \geq 1\}\): не регулярный (лемма о накачке), но КС (PDA)
• \(\{a^n b^n c^n \mid n > 0\}\): не КС (Бар-Хиллель), но вычислим МТ
• \(\{a^n b^n \mid n \geq 1\} \cup \{a^n b^{2n} \mid n \geq 1\}\): КС (NPDA), но не детерминированный КС-язык

1.7 Почему PDA в центре компиляторов

PDA — не только абстракция: они напрямую связаны с построением компиляторов.

1.7.1 PDA и компиляторы

Стек в PDA — политика LIFO. Она как раз подходит для вложенных синтаксических конструкций:

• Арифметика со скобками: (a + (b * c))
• Блочная структура begin/end или {/}
• Цепочки вызовов (каждый вызов — кадр на стек, возврат — снятие)

Типичные фазы компилятора:

• Лексический анализ: токены — часто FSA
• Синтаксический анализ (разбор): грамматика программы — NPDA (КС-грамматики описывают большую часть синтаксиса языков программирования)
• Семантика, генерация кода, оптимизация — дальше

Поэтому синтаксис почти всех ЯП задаёт контекстно-свободной грамматикой, а парсеры — по сути PDA.

1.7.2 Фиксированная и неограниченная память

• FSA: память ограничена числом состояний — не сосчитать произвольное \(n\).
• PDA: состояний конечно, но стек неограничен — можно сосчитать любое \(n\) вталкиваниями.

Для \(L = \{a^n b^n\}\) нужен счёт до произвольного \(n\). FSA с \(k\) состояниями ошибётся при \(n > k\). PDA со стеком справляется для всех \(n\).

1.8 Теория автоматов и модели вычислений

1.8.1 Что такое теория автоматов?

Теория автоматов — раздел теоретической информатики, изучающий:

• Абстрактные математические машины (автоматы) и их вычислительные свойства
• Задачи, которые решают разные типы автоматов

Слово automaton (мн.ч. automata) от греч. αὐτόματον — «самодвижущийся». У Гомера — про автоматические двери и статуи.

1.8.2 Зачем изучать теорию автоматов?

• Автомат — конечное описание языка, который может быть бесконечным
• Автоматы — теоретические модели вычислителей для строгих доказательств о разрешимости и сложности
• Практика: компиляторы, проверка моделей, протоколы, поиск по шаблону

1.8.3 Модели вычислений

Модель вычислений описывает, как из входа получают выход, как устроены память и шаги. Разные модели — разная вычислительная мощность:

Последовательные модели:

• FSA — ограниченная выразительность, фиксированная память; шаблоны, проверка моделей
• PDA — стек, вложенность; основа разбора
• Машина Тьюринга — неограниченная лента чтения-записи; общая последовательная модель

Функциональные модели:

• Лямбда-исчисление — редукция и применение функций

Параллельные модели:

• Сети Петри — параллельные и распределённые системы

Список неполный (регистровые машины, клеточные автоматы и т.д.).

1.8.4 Применения FSA на практике

FSA широко используются:

• Машины Мура/Мили — цифровые схемы
  • Мили по сути FST — выход на переходах
• Лексический анализ: токены
• Диаграммы состояний UML
• Протоколы: турникеты, автоматы, сети

Главное ограничение FSA — фиксированная память: без счёта и без запоминания неограниченного объёма данных.

---

2. Определения

• Конечный преобразователь (FST): FSA с выходом. 7-кортеж \(\langle Q, I, \delta, q_0, F, O, \eta \rangle\), где \(O\) — выходной алфавит, \(\eta: Q \times I \to O^*\) — функция перевода. Перевод только для принятых строк.
• Преобразователь с магазином (PDT): PDA с выходной лентой. 9-кортеж \(\langle Q, I, \Gamma, \delta, q_0, Z_0, F, O, \eta \rangle\), где \(O\) — выходной алфавит, \(\eta: Q \times (I \cup \{\varepsilon\}) \times \Gamma \to O^*\) — функция перевода. Стек хранит информацию и для распознавания, и для перевода.
• Конфигурация PDT: 4-кортеж \(\langle q, x, \gamma, z \rangle\): состояние \(q\), непрочитанный вход \(x\), стек \(\gamma\) (верх первым), уже записанный выход \(z\).
• Функция перевода (\(\eta\)): задаёт выход на переходе. \(\eta(q, i, A) = w\): в \(q\), читая \(i\) при вершине \(A\), записать \(w\). Определена только там, где определена \(\delta\).
• Метка перехода PDT: на стрелке \(i, A/\alpha, w\) (или \(i, A/\alpha : w\)): прочитать \(i\), снять \(A\), втолкнуть \(\alpha\), записать \(w\).
• Замкнутость по операции: класс \(\mathcal{C}\) замкнут по \(\mathcal{O}\), если для любых \(L_1, \ldots, L_n \in \mathcal{C}\) результат \(\mathcal{O}(L_1, \ldots, L_n) \in \mathcal{C}\).
• DPDA (детерминированный PDA): у каждой конфигурации не больше одного продолжения: \(|\delta(q, a, A)| \leq 1\) для всех \(q, a, A\), и \(\delta(q, a, A) \neq \emptyset\) влечёт \(\delta(q, \varepsilon, A) = \emptyset\).
• Детерминированный контекстно-свободный язык (DCFL): язык, распознаваемый некоторым DPDA. Класс DCFL строго вложен в класс CFL.
• Ациклический PDA: для каждого входа \(x\) вычисление \(\langle q_0, x, Z_0 \rangle \vdash^* \langle q, \varepsilon, \gamma \rangle\) всегда завершается; после исчерпания входа \(\varepsilon\)-переходов нет. Любой DPDA эквивалентен ациклическому DPDA.
• Разрушающая память: свойство стека — снятый символ теряется безвозвратно. В отличие от ленты МТ, где чтение не стирает символ.
• Лемма Бар-Хиллеля (накачка для КС-языков): если \(L\) КС, то \(\exists m \geq 1\): любое \(w \in L\), \(|w| \geq m\), раскладывается \(w = x_1 x_2 x_3 x_4 x_5\) с \(|x_2 x_4| > 0\), \(|x_2 x_3 x_4| \leq m\) и \(\forall i \geq 1: x_1 x_2^i x_3 x_4^i x_5 \in L\).
• Теория автоматов: раздел ТКС об абстрактных машинах и разрешимых ими задачах.
• Модель вычислений: математическая схема: как из входа получают выход, как устроены память и шаги. Примеры: FSA, PDA, МТ, \(\lambda\)-исчисление, сети Петри.
• Машина Тьюринга (МТ): модель с бесконечной лентой чтения-записи. Сильнее PDA: память не разрушается при чтении. Общая последовательная модель.
• Контекстно-свободный язык (CFL): язык, распознаваемый (недетерминированным) PDA, эквивалентно порождённый КС-грамматикой. Все регулярные — КС, обратное неверно.

---

3. Формулы

• Формально PDT: \(\text{PDT} = \langle Q, I, \Gamma, \delta, q_0, Z_0, F, O, \eta \rangle\), где \(\delta: Q \times (I \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^*)\) и \(\eta: Q \times (I \cup \{\varepsilon\}) \times \Gamma \to O^*\)
• Переход PDT (по входу): \(\langle q, iy, A\gamma, z \rangle \vdash \langle q', y, \alpha\gamma, zw \rangle\) при \(\delta(q,i,A) = (q',\alpha)\) и \(\eta(q,i,A) = w\)
• Переход PDT (\(\varepsilon\)): \(\langle q, x, A\gamma, z \rangle \vdash \langle q', x, \alpha\gamma, zw \rangle\) при \(\delta(q,\varepsilon,A) = (q',\alpha)\) и \(\eta(q,\varepsilon,A) = w\)
• Условие принятия и перевода PDT: \(\tau(x) = z \iff \langle q_0, x, Z_0, \varepsilon \rangle \vdash^* \langle q_f, \varepsilon, \gamma, z \rangle\) для некоторого \(q_f \in F\)
• Лемма Бар-Хиллеля: для КС \(L\), \(\exists m \geq 1\): \(\forall w \in L\), \(|w| \geq m\), \(\exists\) разбиение \(w = x_1 x_2 x_3 x_4 x_5\) с \(|x_2 x_4| > 0\), \(|x_2 x_3 x_4| \leq m\) и \(\forall i \geq 1: x_1 x_2^i x_3 x_4^i x_5 \in L\)
• Пересечение через разность: \(A \cap B = A \setminus B^c\) (доказательство незамкнутости DPDA по \(\setminus\) из незамкнутости по \(\cap\))
• Де Морган (множества): \(A \cup B = (A^c \cap B^c)^c\)
• Сводка по DPDA: замкнутость только по \({}^c\); нет замкнутости по \(\cup\), \(\cap\), \(\setminus\)

---

4. Примеры

4.1. Построить DPDT, переводящий \(L_1 = \{a^n b^m \mid n \geq 1 \wedge n \leq m\}\) в \(a^n b^n\) (Лаба 7, Задание 1)

Постройте детерминированный преобразователь с магазином, который принимает \(x \in L_1\), где \(L_1 = \{a^n b^m \mid n \geq 1 \wedge n \leq m\}\), и переводит в \(a^n b^n\) (оставить ровно \(n\) символов a и \(n\) символов b, лишние b отбросить).

Показать решение

Идея: на каждое a втолкнуть \(A\) (и вывести a). На фазе b снимать по \(A\) и выводить b — когда стек «опустел» (все \(A\) сопоставлены), дочитывать оставшиеся b без выхода.

DPDT: перевод aⁿbᵐ при n ≤ m в aⁿbⁿ

1. Состояния: \(q_0\) (чтение a), \(q_1\) (чтение b, стек ещё не пуст до \(Z_0\)), \(q_2\) (лишние b после опустошения счётчика — принимающее)

2. Переходы:

   От	К	Метка	Смысл
   \(q_0\)	\(q_0\)	\(a, Z_0/AZ_0, a\)	Втолкнуть \(A\), вывести a
   \(q_0\)	\(q_0\)	\(a, A/AA, a\)	Втолкнуть \(A\), вывести a
   \(q_0\)	\(q_1\)	\(b, A/\varepsilon, b\)	Первое b: снять \(A\), вывести b
   \(q_1\)	\(q_1\)	\(b, A/\varepsilon, b\)	Ещё b: снять \(A\), вывести b
   \(q_1\)	\(q_2\)	\(\varepsilon, Z_0/Z_0, \varepsilon\)	Стек без \(A\): все a сопоставлены, фаза «лишние b»
   \(q_2\)	\(q_2\)	\(b, Z_0/Z_0, \varepsilon\)	Лишние b: игнорировать (без выхода)

3. Принятие: \(q_2\) принимающее (после \(\varepsilon\)-перехода, на стеке только \(Z_0\)). Условие \(n \geq 1\) обеспечивается: без фазы вталкивания в \(q_0\) в \(q_2\) не попасть.

4. Трассировка для \(a^2 b^3\) (\(n=2\), \(m=3\)):

   • a: втолкнуть \(A\), выход a
   • a: втолкнуть \(A\), выход a
   • b: снять \(A\), выход b
   • b: снять \(A\), выход b
   • \(\varepsilon\)-переход в \(q_2\) (на стеке \(Z_0\))
   • b: снять без выхода
   • Конец: \(q_2\) принимает. Выход: \(aabb = a^2 b^2\). ✓

Ответ: \(\tau(a^n b^m) = a^n b^n\) при \(m \geq n \geq 1\). Вывести все a и первые \(n\) символов b; остальные b отбросить.

4.2. Построить DPDT, обращающий строки в \(L_2 = \{xc \mid x \in \{a,b\}^+\}\) (Лаба 7, Задание 2)

Постройте детерминированный преобразователь с магазином, распознающий \(L_2 = \{xc \mid x \in \{a,b\}^+\}\) и переводящий \(xc\) в \(x^R\) (обращение \(x\)).

Показать решение

Идея: LIFO стека даёт обращение. Втолкивать каждый символ \(x\) без выхода. Увидев \(c\), перейти к снятию — выводить каждый снятый символ (обратный порядок).

DPDT: читает xc, выдаёт xᴿ

1. Состояния: \(q_0\) (фаза вталкивания — \(x\)), \(q_1\) (фаза снятия после \(c\)), \(q_2\) (принимающее)

2. Переходы:

   От	К	Метка	Смысл
   \(q_0\)	\(q_0\)	\(a, Z_0/AZ_0, \varepsilon\)	Втолкнуть \(A\), без выхода
   \(q_0\)	\(q_0\)	\(a, A/AA, \varepsilon\)	Втолкнуть \(A\), без выхода
   \(q_0\)	\(q_0\)	\(a, B/AB, \varepsilon\)	Втолкнуть \(A\) под \(B\), без выхода
   \(q_0\)	\(q_0\)	\(b, Z_0/BZ_0, \varepsilon\)	Втолкнуть \(B\), без выхода
   \(q_0\)	\(q_0\)	\(b, B/BB, \varepsilon\)	Втолкнуть \(B\), без выхода
   \(q_0\)	\(q_0\)	\(b, A/BA, \varepsilon\)	Втолкнуть \(B\) под \(A\), без выхода
   \(q_0\)	\(q_1\)	\(c, A/\varepsilon, a\)	\(c\): снять \(A\), вывести a
   \(q_0\)	\(q_1\)	\(c, B/\varepsilon, b\)	\(c\): снять \(B\), вывести b
   \(q_1\)	\(q_1\)	\(\varepsilon, A/\varepsilon, a\)	Снять \(A\), вывести a
   \(q_1\)	\(q_1\)	\(\varepsilon, B/\varepsilon, b\)	Снять \(B\), вывести b
   \(q_1\)	\(q_2\)	\(\varepsilon, Z_0/Z_0, \varepsilon\)	Стек пуст до маркера: принять

3. Трассировка для \(abc\) (\(x = ab\), \(x^R = ba\)):

   • Втолкнуть \(A\), \(B\) (без выхода)
   • Прочитать c: снять \(B\), выход b
   • \(\varepsilon\): снять \(A\), выход a
   • \(\varepsilon\): вершина \(Z_0\) → принять. Выход: \(ba\). ✓

Ответ: \(\tau(xc) = x^R\). Фаза вталкивания для \(x\); фаза снятия даёт \(x^R\).

4.3. Построить DPDT, переводящий \(L_1 = \{a^n b^m a^n \mid n \geq 1, m \geq 1\}\) в \(a^n b^m\) (Лаба 7, Задание 3)

Постройте DPDT, принимающий \(L_1 = \{a^n b^m a^n \mid n \geq 1 \text{ и } m \geq 1\}\) и переводящий в \(a^n b^m\) (отбросить хвост \(a^n\)).

Показать решение

Идея: на ведущие a выводить a и вести счётчик в стеке. На каждое b выводить b. После b на хвостовые a снимать стек без выхода — при совпадении чисел принять.

DPDT: aⁿbᵐaⁿ → aⁿbᵐ

1. Состояния: \(q_0\) (ведущие \(a^n\)), \(q_1\) (\(b^m\)), \(q_2\) (хвостовые \(a^n\)), \(q_3\) (принимающее)

2. Переходы:

   От	К	Метка	Смысл
   \(q_0\)	\(q_0\)	\(a, Z_0/AZ_0, a\)	Ведущее a: втолкнуть \(A\), вывести a
   \(q_0\)	\(q_0\)	\(a, A/AA, a\)	Ещё ведущие a: втолкнуть \(A\), вывести a
   \(q_0\)	\(q_1\)	\(b, A/A, b\)	Первое b: стек не менять, вывести b
   \(q_1\)	\(q_1\)	\(b, A/A, b\)	Ещё b: вывести b, стек не трогать
   \(q_1\)	\(q_2\)	\(a, A/\varepsilon, \varepsilon\)	Первое хвостовое a: снять \(A\), без выхода
   \(q_2\)	\(q_2\)	\(a, A/\varepsilon, \varepsilon\)	Ещё хвостовые a: снять \(A\), без выхода
   \(q_2\)	\(q_3\)	\(\varepsilon, Z_0/Z_0, \varepsilon\)	Стек без \(A\): хвост согласован — принять

3. Трассировка для \(a^2 b^3 a^2\):

   • a, a: втолкнуть \(A\), выход a; то же для второго
   • три b: выход b, b, b (стек \(A, A, Z_0\))
   • два a: снять \(A\), без выхода; снова
   • \(\varepsilon\) → \(q_3\), принять. Выход: \(aabbb = a^2 b^3\). ✓

Ответ: \(\tau(a^n b^m a^n) = a^n b^m\). Вывести ведущие a и все b; хвостовые a только проверить.

4.4. Построить DPDT, переводящий \(L_2 = \{a^i b^j c^k \mid i+k = j\}\) в \(a^i b^i c^k\) (Лаба 7, Задание 4)

Постройте DPDT, принимающий \(L_2 = \{a^i b^j c^k \mid i, j, k \in \mathbb{N}^+, i + k = j\}\) и переводящий в \(a^i b^i c^k\) (оставить только первые \(i\) символов b, «лишние» \(k\) символов b, «оплаченные» символами c, отбросить на выходе).

Показать решение

Идея: из \(i + k = j\) следует \(j = i + k\) символов b. Вывести a, сопоставить ровно \(i\) символов b с втолкнутыми \(A\) (на каждое совпадение выводить b), затем без выхода прочитать ещё \(k\) символов b, затем проверить \(k\) символов c с выводом c.

DPDT: aⁱbʲcᵏ при i + k = j, перевод в aⁱbⁱcᵏ

1. Стратегия:

   • На каждое a втолкнуть \(A\) (вывести a).
   • Сопоставлять b с \(A\) (снять \(A\), вывести b) — после \(i\) символов b на стеке только \(Z_0\).
   • Дальше читать b, вталкивая \(B\) (без выхода) — «лишние» b.
   • Сопоставлять c с \(B\) (снять \(B\), вывести c).
   • Принять, когда и \(A\), и \(B\) исчерпаны по смыслу построения.

2. Состояния: \(q_0\) (a), \(q_1\) (b против \(A\)), \(q_2\) (лишние b, вталкивание \(B\)), \(q_3\) (c против \(B\)), \(q_4\) (принимающее)

3. Переходы:

   От	К	Метка	Смысл
   \(q_0\)	\(q_0\)	\(a, Z_0/AZ_0, a\)	Втолкнуть \(A\), вывести a
   \(q_0\)	\(q_0\)	\(a, A/AA, a\)	Втолкнуть \(A\), вывести a
   \(q_0\)	\(q_1\)	\(b, A/\varepsilon, b\)	Первое b: снять \(A\), вывести b
   \(q_1\)	\(q_1\)	\(b, A/\varepsilon, b\)	Ещё b против \(A\): снять, вывести b
   \(q_1\)	\(q_2\)	\(b, Z_0/BZ_0, \varepsilon\)	Стек без \(A\) (прочитано \(i\) символов b): фаза лишних b
   \(q_2\)	\(q_2\)	\(b, B/BB, \varepsilon\)	Ещё лишние b: втолкнуть \(B\), без выхода
   \(q_2\)	\(q_3\)	\(c, B/\varepsilon, c\)	Первое c: снять \(B\), вывести c
   \(q_3\)	\(q_3\)	\(c, B/\varepsilon, c\)	Ещё c: снять \(B\), вывести c
   \(q_3\)	\(q_4\)	\(\varepsilon, Z_0/Z_0, \varepsilon\)	Всё согласовано: принять

4. Трассировка для \(a^2 b^4 c^2\) (\(i=2\), \(j=4\), \(k=2\), \(i+k = j\) ✓):

   • Втолкнуть \(A, A\), выход a, a
   • Снять \(A\), выход b; снять \(A\), выход b
   • Втолкнуть \(B\), \(B\) (два лишних b)
   • Снять \(B\), выход c; снять \(B\), выход c
   • Вершина \(Z_0\) → принять. Выход: \(aabbcc = a^2 b^2 c^2 = a^i b^i c^k\). ✓

Ответ: \(\tau(a^i b^{i+k} c^k) = a^i b^i c^k\). Две фазы стека: сначала снятие \(A\) против b (с выводом b), затем вталкивание \(B\) для лишних b, затем снятие \(B\) против c (с выводом c).

4.5. Построить DPDT, переводящий \(L_4 = \{a^n b^m \mid n \leq m \leq 2n\}\) в \(a^n b^n\) (Лаба 7, Задание 5)

Постройте DPDT, принимающий \(L_4 = \{a^n b^m \mid m, n \in \mathbb{N}, n \leq m \leq 2n\}\) и переводящий в \(a^n b^n\).

Показать решение

Идея: \(n \leq m \leq 2n\) — число b между \(n\) и \(2n\). Стратегия: на каждое a втолкивать два символа \(A\) на стек (и один раз вывести a). На каждое b снимать один маркер; выводить b только для «первичных» снятий в пределах \(n\).

DPDT: aⁿbᵐ при n ≤ m ≤ 2n, перевод в aⁿbⁿ

Проще: на каждое a — два маркера на стеке, снятие по одному на каждое b. Выход \(a^n b^n\) при корректном диапазоне \(m\).

• Фаза вталкивания: на каждое a — \(A_1\) и \(A_2\). Вывести a.
• Фаза снятия: на каждое b снять один маркер. Выводить b только для первых \(n\) снятий.
• Принятие: когда маркеры исчерпаны при \(n \leq m \leq 2n\).

Упрощённая схема переходов:

Состояния: \(q_0\) (a), \(q_1\) (b, снятие первой «половины» маркеров — с выходом b), \(q_2\) (лишние b, вторая «половина» — без выхода), \(q_3\) (принимающее)

Символы стека: \(P\) (первичный — даёт выход b) и \(S\) (вторичный — без выхода). На каждое a втолкнуть \(P\), затем \(S\).

От	К	Метка	Смысл
\(q_0\)	\(q_0\)	\(a, Z_0/SPZ_0, a\)	Втолкнуть \(P\) и \(S\); вывести a
\(q_0\)	\(q_0\)	\(a, P/SPP, a\)	Втолкнуть \(S\) затем \(P\) над существующим \(P\); вывести a
\(q_0\)	\(q_0\)	\(a, S/SSP, a\)	Втолкнуть \(S\) затем \(P\) над \(S\); вывести a
\(q_0\)	\(q_1\)	\(b, P/\varepsilon, b\)	Первое b по первичному маркеру: снять \(P\), вывести b
\(q_1\)	\(q_1\)	\(b, P/\varepsilon, b\)	Ещё b против \(P\): снять, вывести b
\(q_1\)	\(q_2\)	\(b, S/\varepsilon, \varepsilon\)	b против вторичного: снять \(S\), без выхода
\(q_2\)	\(q_2\)	\(b, S/\varepsilon, \varepsilon\)	Ещё b против \(S\): снять, без выхода
\(q_1\)	\(q_3\)	\(\varepsilon, Z_0/Z_0, \varepsilon\)	Сняты только \(P\) (ровно \(n\) символов b): принять
\(q_2\)	\(q_3\)	\(\varepsilon, Z_0/Z_0, \varepsilon\)	Все маркеры сняты: принять

Ответ: \(\tau(a^n b^m) = a^n b^n\) при \(n \leq m \leq 2n\). Два маркера на стек на каждое a; на каждое b снять один маркер; b на выход только для первичных маркеров; принять при пустоте стека в допустимом диапазоне.

4.6. Замкнутость класса языков DPDA по дополнению — идея построения (Лекция 7, Пример 1)

Объясните, почему класс языков DPDA замкнут по дополнению, и набросайте построение дополняющего DPDA.

Показать решение

Идея: дополнение языка DPDA строится так: (1) сделать DPDA ациклическим, (2) полностью определить \(\delta\), (3) поменять местами принимающие и непринимающие состояния.

1. Почему не работает простой обмен состояний: на входе \(x\) машина может оказаться в непринимающем \(q\), затем \(\varepsilon\)-перейти в принимающее \(q'\). После обмена \(q\) станет принимающим — «дополнение» тоже примет \(x\) — ошибка.
2. Шаг 1 — убрать циклы (ацикличность): преобразовать DPDA так, чтобы после полного чтения входа \(\varepsilon\)-продолжений не было; вычисление заканчивается в однозначном состоянии. Любой DPDA эквивалентен ациклическому (доказательство опускаем; нужно аккуратно убрать \(\varepsilon\)-циклы без смены языка).
3. Шаг 2 — полнота \(\delta\): добавить непринимающее состояние ошибки \(q_{\text{err}}\) и направить туда все неопределённые переходы. Тогда у каждой конфигурации ровно один преемник.
4. Шаг 3 — обмен \(F\) и \(Q\setminus F\): машина полна и ациклична после входа — одно финальное состояние; обмен корректно инвертирует принятие.
5. Итог: дополняющий DPDA распознаёт \(L^c\), если исходный распознаёт \(L\). DPDA замкнут по \({}^c\).

Ответ: замкнутость по дополнению — трёхшаговое построение: ацикличность, полнота \(\delta\), обмен финальными/нефинальными.

4.7. Незамкнутость DPDA по разности — доказательство от противного (Лекция 7, Пример 2)

Докажите, что DPDA не замкнут по разности множеств (\(\setminus\)).

Показать решение

Идея: тождество \(A \cap B = A \setminus B^c\) и замкнутость по дополнение дают противоречие с незамкнутостью по пересечению.

1. Предположим от противного: DPDA замкнут по \(\setminus\).
2. Тождество: для любых \(A, B\): \[A \cap B = A \setminus B^c\]
3. Замкнутости: по дополнению \(B \in \mathbf{DPDA} \Rightarrow B^c \in \mathbf{DPDA}\). По предположению \(A \setminus B^c \in \mathbf{DPDA}\), значит \(A \cap B \in \mathbf{DPDA}\) для любых \(A, B \in \mathbf{DPDA}\).
4. Но мы доказали незамкнутость по \(\cap\) (например \(\{a^n b^n c^m\} \cap \{a^m b^n c^n\} = \{a^n b^n c^n\} \notin \mathbf{DPDA}\)). Противоречие.
5. Вывод: предположение неверно. DPDA не замкнут по \(\setminus\).

Ответ: от противного через \(A \cap B = A \setminus B^c\) и дополнение: из незамкнутости по \(\cap\) следует незамкнутость по \(\setminus\).

4.8. Незамкнутость DPDA по объединению — контрпример (Лекция 7, Пример 3)

Покажите, что класс языков, распознаваемых DPDA, не замкнут по объединению, используя \(L_1 = \{a^n b^n \mid n \geq 1\}\) и \(L_2 = \{a^n b^{2n} \mid n \geq 1\}\).

Показать решение

Идея: \(L_1\) и \(L_2\) по отдельности в \(\mathbf{DPDA}\), но \(L_1 \cup L_2\) не распознаётся DPDA — детерминированная машина не может на фазе a готовиться сразу к двум вариантам числа b.

1. \(L_1 \in \mathbf{DPDA}\): втолкнуть по одному \(A\) на a, затем снимать по одному на b; принять при \(Z_0\) сверху после всех b. Стандартная конструкция.
2. \(L_2 \in \mathbf{DPDA}\): втолкнуть два \(A\) на каждое a, затем снимать по одному на b; принять при \(Z_0\) сверху.
3. \(L_1 \cup L_2 \notin \mathbf{DPDA}\):
   • Читая \(a^n\), DPDA должен «закоммитить» стек под \(n\) или \(2n\) символов b.
   • После a стек фиксирован; число a не перечитать.
   • Детерминированно нельзя одновременно подготовиться к \(n\) и \(2n\) символам b.
   • Формально часто ссылаются на \(\{a^n b^n c^n\} \notin \mathbf{PDA}\) (Бар-Хиллель) и алгебраические приёмы.
4. Вывод: \(L_1 \cup L_2 \notin \mathbf{DPDA}\), значит DPDA не замкнут по \(\cup\).

Ответ: объединение \(\{a^n b^n\} \cup \{a^n b^{2n}\}\) — свидетель незамкнутости по объединению.

4.9. FST — перевод всех строк над \(\{a,b\}\) (Туториал 7, Пример 1)

Постройте конечный преобразователь, принимающий любую строку \(x \in \{a, b\}^*\) и переводящий по правилам \(a \mapsto A\), \(b \mapsto B\) (нижний регистр в верхний).

Показать решение

Идея: все строки принимаются — достаточно одного принимающего состояния с петлями.

Односостоятельный FST: a→A, b→B

1. Компоненты FST:
   • Состояния: \(Q = \{q_0\}\); начальное \(q_0\); \(F = \{q_0\}\)
   • Входной алфавит \(I = \{a, b\}\); выходной \(O = \{A, B\}\)
2. Переходы (петли на \(q_0\)):
   • \(q_0 \xrightarrow{a/A} q_0\): прочитать a, записать A
   • \(q_0 \xrightarrow{b/B} q_0\): прочитать b, записать B
3. Трассировка для \(aba\):
   • a в \(q_0\): выход A, остаться в \(q_0\)
   • b: выход B, остаться
   • a: выход A, остаться
   • Конец входа; \(q_0 \in F\) → принято

Ответ: выход \(ABA\). Одно состояние \(q_0\) (принимающее) с петлями \(a/A\) и \(b/B\).

4.10. FST — перевод только строк без символов b (Туториал 7, Пример 2)

Постройте конечный преобразователь, принимающий строки \(x \in \{a, b\}^*\) без символов b, с переводом \(a \mapsto A\), \(b \mapsto B\). Строки с b отвергаются (перевод не определён).

Показать решение

Идея: стоковое непринимающее состояние после первого b.

FST: только строки без символа b

1. Состояния: \(q_0\) (принимающее — b ещё не было), \(q_1\) (сток — было b)
2. Переходы:
   • \(q_0 \xrightarrow{a/A} q_0\)
   • \(q_0 \xrightarrow{b/B} q_1\): в сток
   • \(q_1 \xrightarrow{a/\varepsilon} q_1\): в стоке без выхода
   • \(q_1 \xrightarrow{b/\varepsilon} q_1\)
3. Трассировка \(aaa\): остаёмся в \(q_0\), выход \(AAA\) → принято, перевод \(AAA\)
4. Трассировка \(aba\): \(q_0 \xrightarrow{a/A} q_0 \xrightarrow{b/B} q_1 \xrightarrow{a/\varepsilon} q_1\) → отвергнуто (перевод не определён)

Ответ: состояния \(\{q_0, q_1\}\), \(q_0\) принимающее. Строки без b переводятся в «верхний регистр»; с b — отвергаются.

4.11. PDT — перевод \(a^n b^n \to A^n B^n\) (Туториал 7, Пример 3)

Постройте преобразователь с магазином для \(L = \{a^n b^n \mid n \geq 1\}\) с переводом \(a \mapsto A\), \(b \mapsto B\), т.е. \(\tau(a^n b^n) = A^n B^n\).

Показать решение

Идея: нужен стек для подсчёта \(n\) и проверки \(n\) символов b. FST не сосчитает произвольное \(n\).

PDT: перевод aⁿbⁿ в AⁿBⁿ

1. Состояния: \(q_0\) (старт), \(q_1\) (a), \(q_2\) (b), \(q_3\) (принимающее)

2. Алфавит стека: \(\Gamma = \{Z_0, A\}\)

3. Переходы:

   От	К	Метка	Смысл
   \(q_0\)	\(q_1\)	\(a, Z_0/AZ_0, A\)	Первое a: втолкнуть \(A\), вывести A
   \(q_1\)	\(q_1\)	\(a, A/AA, A\)	Ещё a: втолкнуть \(A\), вывести A
   \(q_1\)	\(q_2\)	\(b, A/\varepsilon, B\)	Первое b: снять \(A\), вывести B
   \(q_2\)	\(q_2\)	\(b, A/\varepsilon, B\)	Ещё b: снять \(A\), вывести B
   \(q_2\)	\(q_3\)	\(\varepsilon, Z_0/Z_0, \varepsilon\)	Только \(Z_0\) наверху: принять

4. Трассировка для \(aabb\):

   • \(\langle q_0, aabb, Z_0, \varepsilon \rangle \vdash \langle q_1, abb, AZ_0, A \rangle\) (выход A)
   • \(\langle q_1, abb, AZ_0, A \rangle \vdash \langle q_1, bb, AAZ_0, AA \rangle\) (выход A)
   • \(\langle q_1, bb, AAZ_0, AA \rangle \vdash \langle q_2, b, AZ_0, AAB \rangle\) (выход B)
   • \(\langle q_2, b, AZ_0, AAB \rangle \vdash \langle q_2, \varepsilon, Z_0, AABB \rangle\) (выход B)
   • \(\langle q_2, \varepsilon, Z_0, AABB \rangle \vdash \langle q_3, \varepsilon, Z_0, AABB \rangle\) — ПРИНЯТО

Ответ: \(\tau(a^n b^n) = A^n B^n\). Стек считает a, затем сопоставляет b.

4.12. PDT — перевод \(a^n b^n \to b^n\) (Туториал 7, Пример 4)

Постройте детерминированный преобразователь с магазином для \(L = \{a^n b^n \mid n > 0\}\) с переводом \(\tau(a^n b^n) = b^n\) (на выход только «\(b\)-часть», без a).

Показать решение

Идея: на фазе a выводить \(\varepsilon\). На фазе b выводить b на каждое снятие.

PDT: перевод aⁿbⁿ в bⁿ

1. Состояния: \(q_0\) (a), \(q_1\) (b), \(q_F\) (принимающее)

2. Переходы:

   От	К	Метка	Смысл
   \(q_0\)	\(q_0\)	\(a, Z_0/AZ_0, \varepsilon\)	Первое a: втолкнуть \(A\), без выхода
   \(q_0\)	\(q_0\)	\(a, A/AA, \varepsilon\)	Ещё a: втолкнуть \(A\), без выхода
   \(q_0\)	\(q_1\)	\(b, A/\varepsilon, b\)	Первое b: снять \(A\), вывести b
   \(q_1\)	\(q_1\)	\(b, A/\varepsilon, b\)	Ещё b: снять \(A\), вывести b
   \(q_1\)	\(q_F\)	\(\varepsilon, Z_0/Z_0, \varepsilon\)	Стек пуст до маркера: принять, без выхода

3. Трассировка для \(aaabb\) (3 a и 2 b — не в \(L\); возьмём \(aabb\)):

   • Втолкнуть \(A\), \(A\) (без выхода), затем два снятия с выходом b, увидеть \(Z_0\) → принять.
   • Выход: \(bb = b^2\).

Ответ: \(\tau(a^n b^n) = b^n\). Стек считает a; выход только на фазе снятия.

4.13. PDT — перевод \(a^n b^n \to b^n a^n\) (Туториал 7, Пример 5)

Постройте DPDT для \(L = \{a^n b^n \mid n > 0\}\) с переводом \(\tau(a^n b^n) = b^n a^n\) (поменять блоки местами).

Показать решение

Идея: на фазе вталкивания (a) выводить b, на фазе снятия (b) — a.

PDT: перевод aⁿbⁿ в bⁿaⁿ

1. Состояния: \(q_0\) (a), \(q_1\) (b), \(q_F\) (принимающее)

2. Переходы:

   От	К	Метка	Смысл
   \(q_0\)	\(q_0\)	\(a, Z_0/AZ_0, b\)	Первое a: втолкнуть \(A\), вывести b
   \(q_0\)	\(q_0\)	\(a, A/AA, b\)	Ещё a: втолкнуть \(A\), вывести b
   \(q_0\)	\(q_1\)	\(b, A/\varepsilon, a\)	Первое b: снять \(A\), вывести a
   \(q_1\)	\(q_1\)	\(b, A/\varepsilon, a\)	Ещё b: снять \(A\), вывести a
   \(q_1\)	\(q_F\)	\(\varepsilon, Z_0/Z_0, \varepsilon\)	Конец: принять

3. Трассировка для \(aabb\):

   • a: выход b, втолкнуть \(A\)
   • a: выход b, втолкнуть \(A\)
   • b: выход a, снять \(A\)
   • b: выход a, снять \(A\)
   • Вершина \(Z_0\) → принять. Выход: \(bbaa = b^2 a^2\). ✓

Ответ: \(\tau(a^n b^n) = b^n a^n\). На вталкивании — b, на снятии — a.

4.14. DPDA — построение для \(L_1 = \{a^n b^n c^m \mid n, m > 0\}\) (Туториал 7, Пример 6)

Постройте DPDA, распознающий \(L_1 = \{a^n b^n c^m \mid n, m > 0\}\).

Показать решение

Идея: втолкнуть \(A\) на каждое a, сопоставить b, затем принять любое положительное число c (на счётчик c стек не опирается).

DPDA для aⁿbⁿcᵐ

1. Состояния: \(q_0\) (старт), \(q_1\) (a), \(q_2\) (b), \(q_3\) (c, принимающее)

2. Переходы:

   От	К	Метка	Смысл
   \(q_0\)	\(q_1\)	\(a, Z_0/AZ_0\)	Первое a: втолкнуть \(A\)
   \(q_1\)	\(q_1\)	\(a, A/AA\)	Ещё a: втолкнуть \(A\)
   \(q_1\)	\(q_2\)	\(b, A/\varepsilon\)	Первое b: снять \(A\)
   \(q_2\)	\(q_2\)	\(b, A/\varepsilon\)	Ещё b: снять \(A\)
   \(q_2\)	\(q_3\)	\(c, Z_0/Z_0\)	Первое c (сверху \(Z_0\) — a и b согласованы): фаза c
   \(q_3\)	\(q_3\)	\(c, Z_0/Z_0\)	Ещё c

3. Принятие: \(q_3\) принимающее; достижимо только при \(n\) символов b против \(n\) символов a и хотя бы одном c.

Ответ: DPDA с состояниями \(q_0, q_1, q_2, q_3\) (принимающее \(q_3\)) распознаёт \(L_1 = \{a^n b^n c^m \mid n, m > 0\}\).

4.15. DPDA — построение для \(L_2 = \{a^m b^n c^n \mid n, m > 0\}\) (Туториал 7, Пример 7)

Постройте DPDA, распознающий \(L_2 = \{a^m b^n c^n \mid n, m > 0\}\).

Показать решение

Идея: пропустить a (не фиксируют соотношение), затем считать b вталкиваниями, затем проверять c снятиями.

DPDA для aᵐbⁿcⁿ

1. Состояния: \(q_0\) (старт), \(q_1\) (a), \(q_2\) (b), \(q_3\) (c), \(q_4\) (принимающее)

2. Переходы:

   От	К	Метка	Смысл
   \(q_0\)	\(q_1\)	\(a, Z_0/Z_0\)	Первое a: стек не менять
   \(q_1\)	\(q_1\)	\(a, Z_0/Z_0\)	Ещё a
   \(q_1\)	\(q_2\)	\(b, Z_0/BZ_0\)	Первое b: втолкнуть \(B\)
   \(q_2\)	\(q_2\)	\(b, B/BB\)	Ещё b: втолкнуть \(B\)
   \(q_2\)	\(q_3\)	\(c, B/\varepsilon\)	Первое c: снять \(B\)
   \(q_3\)	\(q_3\)	\(c, B/\varepsilon\)	Ещё c: снять \(B\)
   \(q_3\)	\(q_4\)	\(\varepsilon, Z_0/Z_0\)	Сверху только \(Z_0\): все b согласованы с c — принять

3. Принятие: \(q_4\) принимающее, достижимо \(\varepsilon\)-переходом при \(Z_0\) наверху.

Ответ: DPDA с \(q_0, q_1, q_2, q_3, q_4\) (принимающее \(q_4\)) распознаёт \(L_2 = \{a^m b^n c^n \mid n, m > 0\}\).

4.16. Незамкнутость DPDA по пересечению — контрпример (Туториал 7, Пример 8)

Покажите, что \(L_1 \cap L_2 = \{a^n b^n c^n \mid n > 0\}\) для \(L_1 = \{a^n b^n c^m \mid n,m > 0\} \in \mathbf{DPDA}\) и \(L_2 = \{a^m b^n c^n \mid n,m > 0\} \in \mathbf{DPDA}\), и сделайте вывод о незамкнутости DPDA по пересечению.

Показать решение

Идея: оба языка распознаются DPDA (примеры выше). Пересечение — \(\{a^n b^n c^n\}\), не КС-язык (Бар-Хиллель).

1. Пересечение: \[L_1 \cap L_2 = \{a^n b^n c^m\} \cap \{a^m b^n c^n\} = \{a^n b^n c^n \mid n > 0\}\] (Строка в обоих языках тогда и только тогда, когда числа a, b и c совпадают.)
2. Бар-Хиллель для \(\{a^n b^n c^n\}\): пусть язык КС; \(m\) — константа. Возьмём \(w = a^m b^m c^m\). Любое разбиение с \(|x_2 x_3 x_4| \leq m\) пересекает не больше двух групп символов. Накачка вверх (\(i = 2\)) ломает равенство счётчиков. Противоречие. Значит \(\{a^n b^n c^n\} \notin \mathbf{CFL}\), тем более \(\notin \mathbf{DPDA}\).
3. Вывод: \(L_1, L_2 \in \mathbf{DPDA}\), но \(L_1 \cap L_2 \notin \mathbf{DPDA}\). Следовательно DPDA не замкнут по \(\cap\).

Ответ: пересечение \(\{a^n b^n c^n\}\) не КС-язык, значит не распознаётся DPDA. Незамкнутость по пересечению доказана.